package 树;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 完全二叉树的节点个数.java
 * @Description TODO
 * @createTime 2020年10月10日 16:30:00
 * 给出一个完全二叉树，求出该树的节点个数。
 *
 * 说明：
 *
 * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *
 * 示例:
 *
 * 输入:
 *     1
 *    / \
 *   2   3
 *  / \  /
 * 4  5 6
 *
 * 输出: 6
 *方法1.直接递归 不考虑完全二叉树的性质
 *   int result=0;
 *     public int countNodes(TreeNode root) {
 *         if(root==null){
 *             return 0;
 *         }
 *         result++;
 *         countNodes(root.left);
 *         countNodes(root.right);
 *         return result;
 *     }
 *
 * 方法2：先判断是不是满二叉树 不是就正常递归 如果是就用公式计算
 * 如果满二叉树的层数为h，则总节点数为：2^h - 1.
 * 左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。(1 << h1) - 1; 2的n次方-1
 */
public class 完全二叉树的节点个数 {
//    方法2
//    public int countNodes(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        //因为当前树是 complete binary tree
//        //所以可以通过从最左边和从最右边得到的高度判断当前是否是 perfect binary tree
//        TreeNode left = root;
//        int h1 = 0;
//        while (left != null) {
//            h1++;
//            left = left.left;
//        }
//        TreeNode right = root;
//        int h2 = 0;
//        while (right != null) {
//            h2++;
//            right = right.right;
//        }
//        //如果是 perfect binary tree 就套用公式求解
//        if (h1 == h2) {
//            return (1 << h1) - 1;
//        } else {
//            return countNodes(root.left) + countNodes(root.right) + 1;
//        }
}
